type container = User of string 
  | Program of string 
  | Volatile_container of string 
  | Persistent_container of string ;;

type info = Data of int
  | Code of int;;

type property = Max_content of container * info list 
  | Separate of container * info list;;

type ptag = info list list;;

type container_policy = (container * ptag);;

type container_info = (container * info list);;

(* the two following functions sort and eliminate the doubles *)

let rec insert info infolist =
  match (info,infolist) with
      (a,[]) -> [info]
    | (Data(a),Code(b)::tail) -> info::infolist
    | (Code(a),Code(b)::tail) -> if a< b then info::infolist
      else if a>b then Code(b)::(insert info tail) else infolist
    | (Data(a),Data(b)::tail) -> if a< b then info::infolist
      else if a>b then Data(b)::(insert info tail) else infolist
    | (Code(a),Data(b)::tail) -> Data(b)::(insert info tail);;

let rec sort = function
  | []    -> []
  | head::tail -> insert head (sort tail);;

(* subset set1 set2 returns true if set1 is a subset of set2 *)
let rec subset set1 set2 =
  match (set1,set2) with
      ([],_) -> true
    | (_,[]) -> false
    | (Data(a)::tail1,Data(b)::tail2) -> if a < b then false else if a > b then subset set1 tail2 else subset tail1 tail2
    | (Data(a)::tail1,Code(b)::tail2) -> false
    | (Code(a)::tail1,Data(b)::tail2) -> subset set1 tail2
    | (Code(a)::tail1,Code(b)::tail2) -> if a < b then false else if a > b then subset set1 tail2 else subset tail1 tail2;;

(* subelt infolist ptag returns true if infolist is a subset of the info lists of ptag *)
let rec subelt infolist = function
  | [] -> false
  |  head::tail -> if (subset infolist head) then true
    else subelt infolist tail;;

(*substract info infolist returns the info list infolist in which info has been removed*)	
let rec substract info infolist =
  match (info,infolist) with
      (_,[]) -> []
    | (Data(a),Code(b)::tail) -> infolist
    | (Data(a),Data(b)::tail) -> if a < b then infolist else if a > b then Data(b)::(substract info tail) else tail
    | (Code(a),Data(b)::tail) -> Data(b)::(substract info tail)
    | (Code(a),Code(b)::tail) -> if a < b then infolist else if a > b then Code(b)::(substract info tail) else tail ;;


let rec divide elt set = function
[] -> set
  | h::t -> let a = divide elt set t and b =substract h elt in
	    if (subelt b a) then a
	    else b::a;;

let rec clean elt = function
[] -> []
  | h::t -> if (subset h elt) then clean elt t
    else h::(clean elt t);;

let rec divide_check elt = function
[] -> []
  | h::t -> if (subset elt h)
    then (divide h (divide_check elt t) elt)	 
    else h::(clean h (divide_check elt t));;

exception Bad_format_of_property_list;;

let proplist_to_ptag proplist =
  match proplist with 
      [] -> []
    | Max_content(c,max_content)::tail ->
      let rec treat (ptag:ptag) = function
      [] -> ptag
	| head::tail -> match head with 
	    Separate(c,a) -> treat (divide_check a ptag) tail
	    | _ -> raise Bad_format_of_property_list
      in treat [max_content] tail
    | _ -> raise Bad_format_of_property_list;;


(*let c= User("Alice")
  proplist_to_ptag [Max_content(c,[Data(1);Data(2);Data(3);Code(4)]);Separate(c,[Data(1);Data(3);Code(4)])]

  proplist_to_ptag [Max_content(c,[Data 1;Data 2;Data 3;Data 4;Code 1;Code 2;Code 3]);Separate(c,[Data 1;Data 4]);Separate(c,[Data 1;Code 1]);Separate(c,[Data 1;Code 2]);Separate(c,[Data 1;Code 3]);Separate(c,[Data 2;Data 4]);Separate(c,[Data 2;Code 1]);Separate(c,[Data 2;Code 2]);Separate(c,[Data 2; Code 3]);Separate(c,[Data 3;Code 3]);Separate(c,[Data 4;Code 3]);Separate(c,[Code 1;Code 3])]*)


let rec separate set = function
[] -> set
  | h::t -> insert h (separate set t);;

let rec transform = function
[]->[]
  | h::t -> separate (transform t) h;;

let rec explode =function
[] ->[]
  | h::q ->[h]::(explode q);;

let rec minus set = function
[] -> set
  | h::q -> minus (substract h set) q;;

let rec clean2 elt = function
[] -> []
  | h::t -> if (subset elt h) then clean2 elt t
    else h::(clean2 elt t);;

let rec overelt elt = function
[] -> false
  |  h::t -> if (subset h elt) then true
    else overelt elt t;;

let rec add elt set = function
[] -> set
  | h::q -> let a= insert h elt and b = (add elt set q) in
	    if (overelt a b) then  b else a::b;;

let rec analyze max elt= function
[] -> []
  | h::q -> if (subset h elt) 
    then add h (analyze max elt q) (minus max elt) 
    else h::(clean2 h (analyze max elt q));;

let rec compute max set = function
    [] -> set
  | h::q -> compute max (analyze max h set) q;;

let rec add_separate c= function
[] -> []
  | h::t -> Separate(c,h)::(add_separate c t);;

let ptag_to_proplist c ptag= 
  let a= transform ptag in
  Max_content(c,a)::(add_separate c (compute a (explode a) ptag));;


(* Print an itag *)
let rec print_itag = function
  | [] -> ()
  | Data(i)::itag ->
    begin
      print_int i;
      match itag with
	  [] -> ()
	| _ ->
	  print_string " ";
	  print_itag itag
    end
  | _::itag -> print_itag itag;;

(* Print a ptag *)
let rec print_ptag = function
  | [] -> ()
  | infolist::ptags -> print_string "{"; print_itag infolist; print_string "} "; print_ptag ptags;;

(* Print a container policy *)
let rec print_policies = function
  | [] -> ()
  | (Persistent_container(name), policy)::policies ->
      print_string "setpolicy ";
      print_string (name ^ " ");
      print_ptag policy;
      print_newline();
      print_policies policies;
  | _::policies -> print_policies policies;;

 
(* ptag_to_proplist c [[Data 1;Data 2;Data 3];[Data 1;Data 2;Data 4];[Data 2;Data 3;Data 4]]
ptag_to_proplist c [[Data 1;Data 2;Data 3;Data 4];[Data 3;Data 4;Code 1;Code 2];[Code 2;Code 3]]

ptag_to_proplist c [[Data 1;Data 2;Data 3;Data 4];[Data 3;Data 4;Data 5;Data 6];[Data 1;Data 2;Data 5;Data 6]]
proplist_to_ptag [Max_content (User "Alice", [Data 1; Data 2; Data 3; Data 4; Data 5; Data 6]);Separate (User "Alice", [Data 1; Data 3; Data 5]); Separate (User "Alice", [Data 1; Data 4; Data 5]); Separate (User "Alice", [Data 2; Data 3; Data 5]); Separate (User "Alice", [Data 2; Data 4; Data 5]); Separate (User "Alice", [Data 1; Data 3; Data 6]); Separate (User "Alice", [Data 1; Data 4; Data 6]); Separate (User "Alice", [Data 2; Data 3; Data 6]);Separate (User "Alice", [Data 2; Data 4; Data 6])]
ptag_to_proplist c [[Data 2; Data 3; Code 4; Code 6]; [Data 2; Data 3; Code 4; Code 5]; [Data 1; Code 4; Code 6]; [Data 1; Data 3; Code 6]; [Data 1; Code 4; Code 5]; [Data 1; Data 3; Code 5]]
proplist_to_ptag [Max_content (User "Alice", [Data 1; Data 2; Data 3; Code 4; Code 5; Code 6]); Separate (User "Alice", [Data 1; Data 2]); Separate (User "Alice", [Data 1; Data 3; Code 4]); Separate (User "Alice", [Code 5; Code 6])]*)
